package leetcode.code0907;

import java.util.Stack;

/**
 * pass solution2的代码简化
 *
 * @author CaoYu
 * @date 2021年9月28日
 * @description
 */
public class Solution3 extends Solution907 {

	private final int mod = (int) 1e9 + 7;

	@Override
	public int sumSubarrayMins(int[] arr) {
		int len = arr.length;
		if (len == 1)
			return arr[0];
		Stack<Integer> s = new Stack<>();
		long ans = 0;
		for (int i = 0; i < len; i++) {
			while (!s.isEmpty() && arr[s.peek()] >= arr[i]) {
				Integer index = s.pop();
				int rangeLeft = s.isEmpty() ? -1 : s.peek();
				ans += (long) (index - rangeLeft) * (i - index) * arr[index];
				ans %= mod;
			}
			s.add(i);
		}
		while (!s.isEmpty()) {
			Integer index = s.pop();
			int rangeLeft = s.isEmpty() ? -1 : s.peek();
			ans += (long) (index - rangeLeft) * (len - index) * arr[index];
			ans %= mod;
		}
		return (int) (ans % mod);
	}

	private int subArrayNum(int rangeLeft, Integer index, int rangeRight) {
		int left = index - rangeLeft;
		int right = rangeRight - index;
		return left * right;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
